package LeetCode;

public class No74 {
    public static void main(String[] args) {
        int[][] arr = new int[][]{{1}};
        System.out.println(searchMatrix(arr, 1));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int index=0,left=0,right=matrix[0].length-1;
        while(target>matrix[index][right]&&index<matrix.length-1){
            index++;
        }
        if(index==matrix.length) return false;
        while(left<=right){
            int i = (left+right)/2;
            if(matrix[index][i]==target) return true;
            if(matrix[index][i]>target) right=i-1;
            if(matrix[index][i]<target) left=i+1;
        }
        return false;
//        for (int i = 0; i < matrix.length; i++) {
//            for (int j = 0; j < matrix[i].length; j++) {
//                if(matrix[i][j]==target) return true;
//            }
//        }
//        return false;
    }
}
